package zhoujian.oj.leetcode;

/*
 * The count-and-say sequence is the sequence of integers beginning as follows:
 * 		1, 11, 21, 1211, 111221, ...
 * 		1 is read off as "one 1" or 11.
 * 		11 is read off as "two 1s" or 21.
 * 		21 is read off as "one 2, then one 1" or 1211.
 * 
 * Given an integer n, generate the nth sequence.
 * 
 * Note: The sequence of integers will be represented as a string.
 */
public class CountAndSay {
	
	public String countAndSay(int n) {
		if (n < 1) {
			return "";
		}
		
		StringBuilder sb = new StringBuilder("1");
		StringBuilder sub = new StringBuilder();
		
		for (int i = 1; i < n; i++) {
			int length = sb.length();
			for (int j = 0; j < length; j++) {
				int count = 1;
				while (j + 1 < length && sb.charAt(j) == sb.charAt(j + 1)) {
					j++;
					count++;
				}
				sub.append(count);
				sub.append(sb.charAt(j));
			}
			sb = new StringBuilder(sub);
			sub = new StringBuilder();
		}
		
        return sb.toString();
    }

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		CountAndSay countAndSay = new CountAndSay();
		
		assert countAndSay.countAndSay(0).equals("");
		assert countAndSay.countAndSay(1).equals("1");
		assert countAndSay.countAndSay(2).equals("11");
		assert countAndSay.countAndSay(3).equals("21");
		assert countAndSay.countAndSay(4).equals("1211");
		assert countAndSay.countAndSay(5).equals("111221");
	}

}
